#!/usr/bin/env python
# coding: utf-8

import time, random, timeit


def nsum(n):
    start = time.time()
    ans = 0
    for i in range(1, n + 1):
        ans += i
    end = time.time()
    return ans, end - start

def nsum2(n):
    start = time.time()
    s = n * (n + 1) / 2
    end = time.time()
    return s, end - start

def test_nsum(n=100000, nsum=nsum, r=5):
    for i in range(r):
        print '1 + 2 + ... +', n, '= %d (%10.7f sec)' % nsum(n)

def list_min(lst):
    Min = lst[0]
    for x in lst:
        if Min > x:
            Min = x
    return Min

def list_min2(lst):
    return min(lst)

def test_random(func=list_min):
    print 'On random input:'
    for k in range(7):
        n = 10 ** k
        numbers = [random.randint(0, 10000000) for i in range(n)]
        print 'n =', n
        print time_it(func, numbers)

def time_it(f, *args):
    start = time.time()
    result = f(*args)
    end = time.time()
    return result, end - start

def anagram(s1, s2):
    dict1 = dict()
    dict2 = dict()
    for x in s1:
        dict1[x] = s1.count(x)
    for x in s2:
        dict2[x] = s2.count(x)
    return dict1 == dict2

def _test_anagram():
    alphabet = [chr(i) for i in range(ord('a'), ord('z') + 1)]
    string1 = ''.join(alphabet * 1000000)
    string2 = ''.join(random.shuffle(alphabet * 1000000))
    print time_it(anagram, string1, string2)

def from_range(size=1000):
    L = range(size)

def concat(size=1000):
    x = []
    for i in xrange(size):
        x = x + [i]

def self_concat(size=1000):
    x = []
    for i in xrange(size):
        x += [i]

def appnd(size=1000):
    x = []
    for i in xrange(size):
        x.append(i)

def lst_compr(size=1000):
    x = [i for i in xrange(size)]

def from_xrange(size=1000):
    x = list(xrange(size))

def test_func(f, iterations=1000):
    t = timeit.Timer('%s()' % f.func_name,
                     'from homework_sem005 import %s' % f.func_name)
    print f.func_name, t.timeit(number=iterations)

def dummy():
    pass

#test_func(from_range)
#test_func(concat)
#test_func(self_concat)
#test_func(appnd)
#test_func(lst_compr)
#test_func(from_xrange)
#print
#test_func(dummy)

#x = range(int(2e+6))
#pop_head = timeit.Timer('x.pop(0)', 'from __main__ import x')
#pop_tail = timeit.Timer('x.pop()',  'from __main__ import x')
#print 'pop_head:x:', pop_head.timeit(number=1000), 'ms'
#print 'pop_tail:x:', pop_tail.timeit(number=1000), 'ms'

#y = range(int(6e+6))
#pop_head = timeit.Timer('y.pop(0)', 'from __main__ import y')
#pop_tail = timeit.Timer('y.pop()',  'from __main__ import y')
#print 'pop_head:y:', pop_head.timeit(number=1000), 'ms'
#print 'pop_tail:y:', pop_tail.timeit(number=1000), 'ms'

# HW:
# то же самое для
# - обращение по индексу
# - присвоение по индексу (и для словарей)
#

# ф-я, кот получает на вх. список и возвр. k-й наименьший элем.

def ksmallest(lst, k):
    return sorted(lst)[k]
